package com.yeung.swordoffer;

import java.util.Arrays;

/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
 * 输入一个数组,求出这个数组中的逆序对的总数P。
 * 并将P对1000000007取模的结果输出。 即输出P%1000000007
 */
public class 数组中的逆序对 {
    public static void main(String[] args) {
        int arr[] = new int[]{1, 2, 3, 4, 5, 6, 7, 0};
        int res = InversePairs(arr);
        System.out.println(res);
    }

    /**
     * 采用分治法
     *
     * @param array
     * @return
     */
    public static int InversePairs(int[] array) {
        if (array == null || array.length < 1) return 0;
        int result = getReverseCount(array, 0, array.length - 1);
        return result % 1000000007;
    }

    /*归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，
    合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面
    数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - i
    参考剑指Offer，但是感觉剑指Offer归并过程少了一步拷贝过程。
    还有就是测试用例输出结果比较大，对每次返回的count mod(1000000007)求余
    */
    public static int getReverseCount(int[] arr, int low, int high) {
        if (low >= high) return 0;
        int mid = (low + high) / 2;
        //递归求左边的逆序数
        int leftC = getReverseCount(arr, low, mid) % 1000000007;
        //递归求右边的逆序数
        int rightC = getReverseCount(arr, mid + 1, high) % 1000000007;
        //求合起来的逆序数
        int mergeC = merge(arr, low, mid, high);
        return (leftC + rightC + mergeC) % 1000000007;
    }

    /**
     * 统计合并后的逆序对数
     *
     * @param arr
     * @param low
     * @param mid
     * @param high
     * @return
     */
    public static int merge(int[] arr, int low, int mid, int high) {
        int[] lp = Arrays.copyOfRange(arr, low, mid + 1);//to 不包含, 所以要加1
        int[] rp = Arrays.copyOfRange(arr, mid+1, high + 1);//to 不包含, 所以要加1
        int[] part = new int[high - low + 1];
        int li = lp.length - 1, ri = rp.length - 1;
        int pi = part.length - 1;
        int ind = low;
        int count = 0;
        while (li >= 0 && ri >= 0) {
            if (lp[li] > rp[ri]) {
                //左边数组大于右边数组的值, 存在逆序
                count += ri + 1;
                part[pi--] = lp[li--];
                if(count>=1000000007)count%=1000000007;
            } else {
                //无逆序
                part[pi--] = rp[ri--];
            }
        }
        //将剩余的数字复制过去
        while (li >= 0) part[pi--] = lp[li--];
        while (ri >= 0) part[pi--] = rp[ri--];

        //将排好序的tmp的值,一次赋值到原始arr的low开始的局部位置
        for (int i = 0; i < part.length; i++) {
            arr[ind++] = part[i];
        }
        return count%1000000007;
    }


    /**
     * 使用传统方法 时间复杂度 n^2
     *
     * @param array
     * @return
     */
    public static int InversePairs2(int[] array) {
        int[] result = new int[array.length];
        Arrays.fill(result, 0);
        if (array == null || array.length < 1) return result[result.length - 1] % 1000000007;
        result[0] = 0;
        for (int i = 1; i < array.length; i++) {
            int tmp = 0;
            for (int k = 0; k < i; k++) {
                if (array[k] > array[i]) {
                    //逆序了
                    tmp++;
                }
            }
            result[i] = result[i - 1] + tmp;
        }
        return result[result.length - 1] % 1000000007;
    }

}
